/**
 * @file 51.NQueens.cc
 * @author snow-tyan (zziywang@163.com)
 * @brief {Life is too short to learn cpp.}
 * @version 0.1
 * @date 2021-11-15
 * 
 * @copyright Copyright (c) 2021
 * 
 * 棋盘问题
 * 51.N皇后
 * 37.解数独 -- 太难了吧
 */

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
// #define NQUEEN

template <typename T>
void print(const T &Containers)
{
    typename T::const_iterator it = Containers.begin();
    while (it != Containers.end()) {
        // cout << *it << " ";
        cout << *it << endl;
        ++it;
    }
    cout << endl;
}

#ifdef NQUEEN
class Solution
{
public:
    vector<vector<string>> res;

public:
    // 51. N*N的棋盘上摆N个皇后
    // 这些皇后不能同行、不能同列、不能同斜线（45°，135°）
    vector<vector<string>> solveNQueens(int n)
    {
        vector<string> chessboard(n, string(n, '.'));
        backtracking51(chessboard, 0, n);
        return res;
    }

private:
    bool isValid(vector<string> &chessboard, int row, int col, int n)
    {
        // 剪枝，只需检查到当前行row
        // 行不用检查
        // 检查列
        for (int i = 0; i < row; ++i) {
            if (chessboard[i][col] == 'Q') {
                return false;
            }
        }
        // 检查左上，即135度
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; --i, --j) {
            if (chessboard[i][j] == 'Q') {
                return false;
            }
        }
        // 检查右上，即45度
        for (int i = row - 1, j = col + 1; i >= 0 && j < n; --i, ++j) {
            if (chessboard[i][j] == 'Q') {
                return false;
            }
        }
        return true;
    }

    void backtracking51(vector<string> &chessboard, int row, int n)
    {
        if (row == n) {
            res.emplace_back(chessboard);
            return;
        }
        for (int col = 0; col < n; ++col) { // dim=1方向-->
            if (!isValid(chessboard, row, col, n)) {
                continue;
            }
            chessboard[row][col] = 'Q';
            backtracking51(chessboard, row + 1, n); // dim=0方向 向下
            chessboard[row][col] = '.';
        }
    }
};
#endif

class Solution
{
public:
    void solveSudoku(vector<vector<char>> &board)
    {
        // 9*9 棋盘
        backtracking(board);
    }

private:
    bool isValid(vector<vector<char>> &board, int row, int col, char val)
    {
        for (int j = 0; j < 9; ++j) {
            if (board[row][j] == val) {
                return false;
            }
        }
        for (int i = 0; i < 9; ++i) {
            if (board[i][col] == val) {
                return false;
            }
        }
        int innerRow = row / 3 * 3;
        int innerCol = col / 3 * 3;
        for (int i = innerRow; i < innerRow + 3; ++i) {
            for (int j = innerCol; j < innerCol + 3; ++j) {
                if (board[i][j] == val) {
                    return false;
                }
            }
        }
        return true;
    }

    bool backtracking(vector<vector<char>> &board)
    {
        for (int i = 0; i < 9; ++i) {
            for (int j = 0; j < 9; ++j) {
                // 空格才需要填
                if (board[i][j] != '.') {
                    continue;
                }
                // 尝试放置1-9
                // 采坑：不能写num<'10'，这个字符不和1-9连续
                for (char num = '1'; num <= '9'; ++num) { 
                    if (!isValid(board, i, j, num)) {
                        continue;
                    }
                    board[i][j] = num;
                    // 找到一个可能的数立即返回
                    if (backtracking(board)) { 
                        return true;
                    }
                    board[i][j] = '.';
                }
                // 1-9都尝试完了
                return false;
            }
        }
        return true;
    }
};

Solution solve = Solution();

#ifdef NQUEEN
void test51()
{
    auto res = solve.solveNQueens(4);
    for (auto &r : res) {
        print(r);
    }
}
#endif

int main()
{
    // test51();
    return 0;
}